1. Field of the Invention
This invention reveals a reduced-width multiplier capable of minimizing errors. Specifically, this invention relates to a reduced-width multiplier capable of processing digital signals of communication system such as a timing recovery circuit, a carrier recovery circuit and a FIR filter.
2. Description of the Related Prior Art
In the face of the recent fast progress in communication, computation methods have become more complicated. The demand for multipliers is escalating, and efficient multiplier design is deemed important. A currently important topic is how to design a multiplier characterized by low power and area-saving, while meeting the requirements of integrated circuit design and its applications.
The operation of a multiplier is basically the expansion of a multiplicand(104), according to the value of a multiplicator (100), resulting in a parallelogram as shown in FIG. 1. The construction involves several steps. Expand a multiplicand(104) in accordance with a multiplicator(100), arrange them by positional weight, and finally add up all the values found in the summation row to produce a product (105). The summation row includes two parts, i.e. the sum of low bits (LP, 101) and the sum of high bits(MP, 102). If a multiplicand X has a bit length of m, and a multiplicator Y has a bit length of n, then the product PD will have (m+n) bits. With regards to the application of digital communication, the bit number (m+n−p) required by a product is not necessarily (m+n), but some where in between max(m,n) and(m+n). The bit number required by a product also depends on area, computation speed and performance required by the system, such as signal-to-noise ratio (SNR), and bit error ratio (BER), etc. In general, the first (m+n−p) bits are taken and constitute the most significant bits. As illustrated in FIG. 1, this invention uses p=n, and error arises between the value obtained by taking (m+n−p) bits and the value resulting from taking (m+n) bits.
Therefore, this invention tackles the existing difficulties associated with saving area space while reducing errors. As far as the (m+n−p) bits we need, this invention uses the first (m+n−p) bits while assigning 0 directly to the lower P bits without any computation, when it comes to Integer fixed-point; or it simply takes the first (m+n−p) bits generated by this invention when fractional fixed-points are involved.
Amongst existing integrated circuit designs, Array and Booth multipliers are commonly used when it comes to fast computation. With regards to signal processing in digital communication, the bit length of a product term is reduced and determined in response to the SNR required by the system. When the bit number of the product is decreased, the computation required is also reduced. At present, there are four types of technology in this regard. FIGS. 2 to 5 illustrate the four methods, using an example of 5×5 with product of six bit integers (m=n=5, p=4).
FIG. 2 illustrates method 1 or a Rounded Method. Calculation is done on all product terms (202) up to (m+n) bits. After that, the results between the PD(m+n−1) bits and the PDp bits are reserved. This is also known as a Truncated Method. Alternatively, a Rounded Method could be used, which includes rounding off the PD(p−1) term of the result, and adding it to the preceding term. This method is generally adopted by most systems. Complete computation followed by truncation will yield a result, and the error between the result and the original product will be smaller. However, truncating a great amount of product terms which have undergone all of the computation not only waste computation time, but also waste the computational hardware area.
FIG. 3 illustrates method 2 which involves truncation followed by computation. Unlike method 1, this method involves truncating the bit number of a multiplicand and a multiplicator, so as to conform with the requirement of the system regarding the bit number of product (302). After truncation, the multiplicand and the multiplicator will undergo computation in a traditional multiplier. For example, if both the multiplicator(100) and the multiplicand(104) consists of five bits respectively, while the system requires six bits, they will be truncated to three bits respectively. In other words, a 5×5 multiplier is reduced to a 3×3 multiplier, in order to decrease the area. The drawback of this method is that, the bits of a multiplicator and a multiplicand are truncated before computation, leading to the removal of those multiplicators or multiplicands located in relatively higher weighting positions, such as X1Y4, X4Y1 . . . (301) and therefore yielding a great error.
FIG. 4 illustrates method 3 , which involves compensation with a fixed value. In view of the error derived from truncating operation units of relatively low bits, the product is compensated with a fixed value. In this computation, the value to be removed is always found behind the bit of the product term to be removed. The fixed value of compensation is a result of the statistics conducted on the bit number of multiplicator (100)s and multiplicands (104)s. Good examples of this kind are found in the content of U.S. Pat. No. 4,598,382 and in Kidambi, S. S. et al. (IEEE Transactions on Circuits and Systems II, Vol. 43, No. 2, pp. 90˜95,1996). Its underlying theory is that a certain bit length always yields a certain error, and hence it figures out a product (403) by adding in a fixed value. The example in FIG. 4 uses a fixed compensation value (402) of 1. The error produced in this method is smaller than that in method 2, which involves truncation prior to compensation. This method also reduces computation and hardware area. However, due to the fact that a fixed compensation value independent of the multiplicand or the multiplicator is added to the product, the error may still be large. For instance, if both the multiplicator and the multiplicand are 0, then the product will be zero. However, this method will still compensate the product with a fixed value. Thus, although the average error of this method will be smaller than that produced by truncation followed by computation, considerable errors will still exist in the product for some cases.
FIG. 5 illustrates method 4 which involves compensation with an adaptive value. Jou, J. M. et al. (IEEE Transactions on Circuits and Systems II, Vol. 46, No. 6, pp. 836˜842, 1999) figured out a compensation method wherein the value added to the product term depends on the distribution of the input signals of the multiplicator (100) and the multiplicand (104). This method yields an average error or an individual error much smaller than that of method 3 (compensation of fixed value). Nevertheless, Jou, J. M. et al. did not completely take into account the distribution of input signals and the distribution of the intended compensation, leading to a surplus of hardware area in the compensating circuit as well as unnecessary power consumption.
This invention keeps all the merits of the above circuits and creates an innovative compensating circuit. It reduces not only power consumption due to the reduction of computation and hardware, but it also generates a post- compensation product with error smaller than that found in the design of Jou, J. M. et al.